package 树.普通二叉树;

import 树.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by yang on 2016/8/26.
 */
public class BinaryTree {

    private TreeNode root = null;

    public BinaryTree(TreeNode root) {
        this.root = root;
    }

    /**
     * Traverse binary tree with the algorithm of depth-first.
     * beside with {@code LinkedList},we can use {@ConcurrentLinkedQueue}
     * or {@code LinkedBlockingQueue}
     * {@code LinkedList} is muti-thread unsafe.
     * {@ConcurrentLinkedQueue} is muti-thread safe.
     * @param treeNode : root of the binary tree ready to traverse
     */
    public void depTraverse(TreeNode treeNode) {

        Queue<TreeNode> queue = new LinkedList<>();
        if (treeNode != null) {
            queue.offer(treeNode);
        }
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            System.out.println(tmp.val);
            if (tmp.lChild !=null) {
                queue.offer(tmp.lChild);
            }

            if (tmp.rChild != null) {
                queue.offer(tmp.rChild);
            }
        }
    }

    /**
     * Traverse binary tree with the algorithm of preorder-first
     * @param treeNode : root of the tree ready to traverse
     */
    public void preTraverse(TreeNode treeNode) {

        if (treeNode != null) {
            System.out.println(treeNode.val);
            preTraverse(treeNode.lChild);
            preTraverse(treeNode.rChild);
        }
    }

    /**
     * Traverse binary tree with the algorithm of inOrder-first
     * @param treeNode : root of the tree ready to traverse
     */
    public void inTraverse(TreeNode treeNode) {

        if (treeNode != null) {
            inTraverse(treeNode.lChild);
            System.out.println(treeNode.val);
            inTraverse(treeNode.rChild);
        }
    }

    /**
     * Traverse binary tree with the algorithm of postOrder-first
     * @param treeNode :  root of the tree ready to traverse
     */
    public void postTraverse(TreeNode treeNode) {

        if (treeNode != null) {
            postTraverse(treeNode.lChild);
            postTraverse(treeNode.rChild);
            System.out.println(treeNode.val);
        }
    }

    /**
     * create binary tree with the algorithm of depth-first
     * @param val : value of ready to insert
     * @return new tree node
     */
    public TreeNode insertOfinOrder(int val) {

        TreeNode nodeOfInsert = new TreeNode(val);

        if (root == null) {
            root = nodeOfInsert;
        } else {
            TreeNode current = root;
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.offer(current);

            while (!queue.isEmpty()) {
                TreeNode tmp = queue.poll();
                if (tmp.lChild != null) {
                    queue.offer(tmp.lChild);
                } else {
                    tmp.lChild = nodeOfInsert;
                    break;
                }

                if (tmp.rChild != null) {
                    queue.offer(tmp.rChild);
                } else {
                    tmp.rChild = nodeOfInsert;
                    break;
                }
            }
        }

        return root;
    }
}
